package leetcode.code0954;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：29 ms, 在所有 Java 提交中击败了81.09%的用户
//
//内存消耗：48.9 MB, 在所有 Java 提交中击败了5.97%的用户
//
//通过测试用例：102 / 102
public class Solution implements IDebug {

	public boolean canReorderDoubled(int[] arr) {
		Arrays.sort(arr);
		Map<Integer, Integer> hash = new HashMap<>();
		int db = 0;
		for (int num : arr) {
			if (num < 0) {
				int size = hash.getOrDefault(db = num << 1, 0);
				if (size == 0) {
					int add = hash.getOrDefault(num, 0);
					hash.put(num, add + 1);
				} else if (size == 1) {
					hash.remove(db);
				} else {
					hash.put(db, size - 1);
				}
			} else {
				if ((num & 1) == 1) {
					int add = hash.getOrDefault(num, 0);
					hash.put(num, add + 1);
				} else {
					int size = hash.getOrDefault(db = num >> 1, 0);
					if (size == 0) {
						int add = hash.getOrDefault(num, 0);
						hash.put(num, add + 1);
					} else if (size == 1) {
						hash.remove(db);
					} else {
						hash.put(db, size - 1);
					}
				}
			}

		}
		return hash.size() == 0;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(false, this.canReorderDoubled(HelpDebug.str2array3("[3,1,3,6]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(false, this.canReorderDoubled(HelpDebug.str2array3("[2,1,2,6]")));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(true, this.canReorderDoubled(HelpDebug.str2array3("[4,-2,2,-4]")));

	}

	@Override
	public void debug4() {
		HelpDebug.compare(false, this.canReorderDoubled(HelpDebug.str2array3("[1,2,4,16,8,4]")));

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
